package elementaryAlgorithm;


import java.util.*;

/**
 * 101. 对称二叉树
 * @描述
 * 给定一个二叉树，检查它是否是镜像对称的。
 *
 *  
 *
 * @例如
 * 二叉树 [1,2,2,3,4,4,3] 是对称的。
 *
 *     1
 *    / \
 *   2   2
 *  / \ / \
 * 3  4 4  3
 *  
 *
 * 但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
 *
 *     1
 *    / \
 *   2   2
 *    \   \
 *    3    3
 *  
 *
 * @进阶
 *
 * 你可以运用递归和迭代两种方法解决这个问题吗？
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/symmetric-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * */
public class SymmetricBinaryTree {
    public static void main(String[] args) {
        /*TreeNode node4 = new TreeNode(3);
        TreeNode node5 = new TreeNode(4);
        TreeNode node6 = new TreeNode(4);
        TreeNode node7 = new TreeNode(3);
        TreeNode node2 = new TreeNode(2,node4,node5);
        TreeNode node3 = new TreeNode(2,node6,node7);
        TreeNode root = new TreeNode(1,node2,node3);*/

        TreeNode node4 = new TreeNode(3);
        TreeNode node7 = new TreeNode(3);
        TreeNode node2 = new TreeNode(2,null,node4);
        TreeNode node3 = new TreeNode(2,null,node7);
        TreeNode root = new TreeNode(1,node2,node3);

        SymmetricBinaryTree symmetricBinaryTree = new SymmetricBinaryTree();
        boolean symmetric = symmetricBinaryTree.isSymmetric(root);
        System.out.println(symmetric);
    }

    public boolean isSymmetric(TreeNode root) {
        List<Integer> pre1 = new ArrayList<>();
        List<Integer> pre2 = new ArrayList<>();
        /*preOrder(root,pre1);
        preOrderNext(root,pre2);*/

        preOrderIteration(root,pre1);
        preOrderIterationNext(root,pre2);
        for (int i = 0; i < pre1.size(); i++) {
            if (pre1.get(i) == null && pre2.get(i) == null){
                continue;
            }else if((pre1.get(i) == null && pre2.get(i) != null) || (pre1.get(i) != null && pre2.get(i) == null)){
                return false;
            }else if (pre1.get(i).intValue() != pre2.get(i).intValue()){
                return false;
            }
        }

        List<Integer> mid1 = new ArrayList<>();
        List<Integer> mid2 = new ArrayList<>();
        midOrderIteration(root,mid1);
        midOrderIterationNext(root,mid2);
        for (int i = 0; i < mid1.size(); i++) {
            if (mid1.get(i) == null && mid2.get(i) == null){
                continue;
            }else if((mid1.get(i) == null && mid2.get(i) != null) || (mid1.get(i) != null && mid2.get(i) == null)){
                return false;
            }else if (mid1.get(i).intValue() != mid2.get(i).intValue()){
                return false;
            }
        }
        return true;
    }

    public List<Integer> preOrder(TreeNode root, List<Integer> result){
        if (root == null){
            result.add(null);
            return result;
        }
        result.add(root.val);
        preOrder(root.left,result);
        preOrder(root.right,result);
        return result;
    }

    public List<Integer> preOrderNext(TreeNode root, List<Integer> result){
        if (root == null){
            result.add(null);
            return result;
        }
        result.add(root.val);
        preOrderNext(root.right,result);
        preOrderNext(root.left,result);
        return result;
    }

    public List<Integer> midOrder(TreeNode root, List<Integer> result){
        if (root == null){
            result.add(null);
            return result;
        }
        midOrder(root.left,result);
        result.add(root.val);
        midOrder(root.right,result);
        return result;
    }

    public List<Integer> midOrderNext(TreeNode root, List<Integer> result){
        if (root == null){
            result.add(null);
            return result;
        }
        midOrderNext(root.right,result);
        result.add(root.val);
        midOrderNext(root.left,result);
        return result;
    }


    /**
     * 先序遍历迭代解法
     * */
    public List<Integer> preOrderIteration(TreeNode root, List<Integer> result){
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node = root;
        queue.add(node);
        while(!queue.isEmpty()){
            node = queue.remove();
            result.add(node.val);
            if (node.left != null){
                queue.add(node.left);
            }
            if (node.right != null){
                queue.add(node.right);
            }
        }
        return result;
    }

    /**
     * 先序遍历迭代解法
     * */
    public List<Integer> preOrderIterationNext(TreeNode root, List<Integer> result){
        Queue<TreeNode> queue = new LinkedList<>();
        TreeNode node = root;
        queue.add(node);
        while(!queue.isEmpty()){
            node = queue.remove();
            result.add(node.val);
            if (node.left != null){
                queue.add(node.right);
            }
            if (node.right != null){
                queue.add(node.left);
            }
        }
        return result;
    }

    /**
     * 中序遍历迭代解法
     * */
    public List<Integer> midOrderIteration(TreeNode root, List<Integer> result){

        TreeNode node = root;
        Stack<TreeNode> stack = new Stack<>();
        while(node != null || !stack.isEmpty()){
            if (node != null){
                stack.add(node);
                node = node.left;
            }else {
                node = stack.pop();
                result.add(node.val);
                node = node.right;
            }
        }
        return result;
    }

    /**
     * 中序遍历迭代解法
     * */
    public List<Integer> midOrderIterationNext(TreeNode root, List<Integer> result){
        TreeNode node = root;
        Stack<TreeNode> stack = new Stack<>();
        while(node != null || !stack.isEmpty()){
            if (node != null){
                stack.add(node);
                node = node.right;
            }else {
                node = stack.pop();
                result.add(node.val);
                node = node.left;
            }
        }
        return result;
    }
}

/**
 * 题解
 * */
class SymmetricBinaryTreeAnswer{
    public boolean isSymmetric(TreeNode root) {
        return false;
    }
}